ICPC Live Archive/3130 - Pipes/pipes_oh.cpp

   1 // Sample solution of NWERC-2004-Pipes by Ola Hugosson
   2 #include <stdio.h>
   3 #include <assert.h>
   4 #include <iostream>
   5 using namespace std;
   6
   7 #define D(x) cout << #x " = " << (x) << endl
   8
   9 #define NONE  0
  10 #define IN    1
  11 #define OUT   2
  12 #define FEDECOST 0xfede
  13 #define MAXSTATES 5798 // pre-calculated
  14 #define GETTYPE(sidx,i) (((sidx)>>(2*(i)))&3)
  15 #define SETTYPE(type,i) (((type)<<(2*(i))))
  16
  17 int state[MAXSTATES], newstate[MAXSTATES], map[MAXSTATES];
  18 short invmap[1<<(2*11)];
  19
  20 // calculate a map used to enumerate all valid boundaries
  21 int genmap(int c, int n, int i, int nest, int sidx)
  22 {
  23     printf("c = %d, n = %d, i = %d, nest = %d, sidx = %x\n", c, n, i, nest, sidx);
  24     if (nest>=0 && i<=c) {
  25         n=genmap(c,n,i+1,nest,  sidx|SETTYPE(NONE,i));
  26         n=genmap(c,n,i+1,nest+1,sidx|SETTYPE(IN,i));
  27         n=genmap(c,n,i+1,nest-1,sidx|SETTYPE(OUT,i));
  28     }
  29     else if (nest==0){
  30         map[n++]=sidx;
  31         printf("mask = %X, nest = 0\n", sidx);
  32     }
  33     assert(n<=MAXSTATES);
  34     return n;
  35 }
  36
  37 int main(){
  38     int floors, r, c, x, y, n, i, j, sidx, left, up, right, down, cost, prevcost;
  39     char lrwall[30],udwall[30];
  40     for( scanf("%d",&floors); floors--;) {
  41         scanf("%d %d\n",&r,&c);
  42         gets(udwall); //dummy-input
  43         n=genmap(c,0,0,0,0);
  44
  45         for (int i = 0; i < n; ++i){
  46             int mask = map[i];
  47             printf("mask = %X\n", mask);
  48             for (int j = 0; j <= c; ++j){
  49                 int what = GETTYPE(mask, j);
  50                 switch (what){
  51                     case NONE:
  52                     cout << "NONE ";
  53                     break;
  54                     case IN:
  55                     cout << "IN ";
  56                     break;
  57                     case OUT:
  58                     cout << "OUT ";
  59                     break;
  60                 }
  61             }
  62             cout << endl;
  63         }
  64
  65         for(i=0; i<n; i++) {
  66             invmap[map[i]]=i;
  67             newstate[i]=FEDECOST;
  68         }
  69         newstate[invmap[0]]=0;
  70         for(y=0; y<r; y++) {
  71             gets(lrwall);
  72             gets(udwall);
  73             for(x=0; x<c; x++) {
  74                 for(i=0; i<n; i++) {
  75                     state[i]=newstate[i];
  76                     newstate[i]=FEDECOST;
  77                 }
  78                 for(i=0; i<n; i++) {
  79                     static const char lut[3][3][3] =
  80                         {{{1, IN,   OUT }, {2, NONE, IN  }, {2, NONE, OUT }},
  81                         {{2, NONE, IN  }, {1, NONE, NONE}, {0, NONE, NONE}}, // the 0 prevents internal loops
  82                         {{2, NONE, OUT }, {1, NONE, NONE}, {1, NONE, NONE}}};
  83                     prevcost = (x>0 ? state[i] : ((map[i]&3)==NONE) ? state[invmap[map[i]>>2]] : FEDECOST);
  84                     if (prevcost>=FEDECOST)
  85                         continue; // speed up somewhat
  86                     sidx=map[i];
  87                     left=GETTYPE(sidx,x);
  88                     up  =GETTYPE(sidx,x+1);
  89                     for(j=0; j<lut[left][up][0]; j++) {
  90                         down =lut[left][up][1+j];
  91                         right=lut[left][up][2-j];
  92                         cost = prevcost + (right==NONE ? 0 : lrwall[2*x+2]-'0') +
  93                             (down ==NONE ? 0 : udwall[2*x+1]-'0');
  94                         if (left==up && left!=NONE) { // find matching IN/OUT pair
  95                             int nest=0, xx=(left==OUT)? x : x+1;
  96                             while(nest += GETTYPE(sidx,xx)==OUT ? -1 : GETTYPE(sidx,xx)==IN ? +1 : 0)
  97                                 xx += nest<0 ? -1 : 1;
  98                             sidx ^= SETTYPE(3,xx);  // toggle IN<->OUT
  99                         }
 100                         sidx = sidx & ~SETTYPE(15,x) | SETTYPE(down,x) | SETTYPE(right,x+1);
 101                         if (cost<newstate[invmap[sidx]])
 102                             newstate[invmap[sidx]]=cost;
 103                     }
 104                 }
 105             }
 106         }
 107         printf("%d\n",state[invmap[(IN<<(2*c-2))|(OUT<<(2*c))]]);
 108     }
 109     return 0;
 110 }